package two.chapter_4.c4_3;

import edu.princeton.cs.algs4.MinPQ;
import two.chapter_1.c1_3.LinkedQueue;
import two.chapter_1.c1_3.Queue;

/**
 * 延迟版本 ：最小生成树
 */
public class LazyPrimMST extends MST {
    private double weight;
    private boolean[] marked;//最小生成树顶点
    private Queue<Edge> mst;//最小生成树的边
    private MinPQ<Edge> pq;//横切边
    public LazyPrimMST(EdgeWeightedGraph g) {
        super(g);

        pq = new MinPQ<>();
        mst = new LinkedQueue<>();
        marked = new boolean[g.v()];
        visit(g, 0);
        while (!pq.isEmpty()){

            Edge min= pq.delMin();
            int v=min.either();
            int w=min.other(v);
            if (marked[v] && marked[w])
                continue;

            weight+=min.weight();
            mst.enqueue(min);
            if (!marked[v])
                visit(g,v);
            if (!marked[w])
                visit(g,w);
        }
    }

    protected void visit(EdgeWeightedGraph g, int v) {
        marked[v] = true;
        for (Edge edge : g.adj(v)) {
            if (!marked[edge.other(v)])
                pq.insert(edge);
        }

    }

    @Override
    public Iterable<Edge> edges() {
        return mst;
    }

    @Override
    public double weight() {
        return weight;
    }
}
